package Array.Medium;

import java.util.HashMap;

public class LC0238 {
    /**
     * 这个解法利用了nums[i]∈[-30,30]的特性，存储了每个数字出现的次数。对于结果数组上的每一个位置i，都可以遍历[-30,30]，
     * 按照存储的出现次数计算乘方；nums[i]的出现次数要少算一次。
     */
    public int[] productExceptSelf(int[] nums) {
        HashMap<Integer, Integer> numberOccurrenceMap = new HashMap<>();
        for (int num : nums) {
            numberOccurrenceMap.put(num, numberOccurrenceMap.getOrDefault(num, 0) + 1);
        }

        int N = nums.length;
        int[] ret = new int[N];
        for (int i = 0; i < N; i++) {
            int product = 1;
            for (int num = -30; num <= 30; num++) {
                int occurrence = numberOccurrenceMap.getOrDefault(num, 0);
                if (num == nums[i]) occurrence--;
                product *= (int) Math.pow(num, occurrence);
            }

            ret[i] = product;
        }

        return ret;
    }

    /**
     * 利用前缀积、后缀积的优化版本
     */
    public int[] productExceptSelfPrefixProduct(int[] nums) {
        int N = nums.length;
        int[] ret = new int[N];
        ret[0] = 1;
        ret[1] = nums[0];
        for (int i = 2; i < N; i++) { // 计算前缀积
            ret[i] = ret[i - 1] * nums[i - 1]; // ret[i]目前存储的是nums[0~i-1]的积
        }

        int postfixProduct = 1; // 累积后缀积
        for (int i = N - 2; i >= 0; i--) {
            postfixProduct *= nums[i + 1];
            ret[i] = ret[i] * postfixProduct; // 补上后缀部分，得到除自身以外数字的乘积
        }

        return ret;
    }
}
